package leetcode.Hot100;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * @author Cheng Jun
 * Description: 给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，为避免会议冲突，
 * 同时要考虑充分利用会议室资源，请你计算至少需要多少间会议室，才能满足这些会议安排。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/meeting-rooms-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2022/1/7 13:20
 */
public class minMeetingRooms {
    // 1 <= intervals.length <= 104
    // 0 <= starti < endi <= 106

    // 输入：intervals = [[0,30],[5,10],[15,20]]
    // 输出：2
    static public int minMeetingRooms(int[][] intervals) {
        int res = 1;
        int freeRoom = 0;
        PriorityQueue<Integer> endTimeQueue = new PriorityQueue<>();
        // 按照 开始时间排序
        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
        for (int i = 0; i < intervals.length - 1; i++) {
            while (!endTimeQueue.isEmpty() && intervals[i + 1][0] >= endTimeQueue.peek()) {
                endTimeQueue.poll();
                // 空出一个房间
                freeRoom++;
            }
            if (intervals[i][1] > intervals[i + 1][0]) {
                endTimeQueue.add(intervals[i][1]);
                if (freeRoom > 0) {
                    freeRoom--;
                } else {
                    res++;
                }
            }
        }
        return res;
    }

    // 小根堆的极致应用
    public int minMeetingRooms1(int[][] intervals) {
        PriorityQueue<Integer> q = new PriorityQueue<>();
        // 按照会议开始时间排序
        Arrays.sort(intervals, Comparator.comparingInt(interval -> interval[0]));
        q.add(intervals[0][1]);
        for(int i = 1; i < intervals.length; i++){
            // 看看有没有最先 空出来的房间
            if(q.peek() <= intervals[i][0]){
                q.poll();
            }
            // 加入会议结束时间
            q.add(intervals[i][1]);
        }
        return q.size();
    }
}
